{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "inputs = [[1,2,2,1],\n",
    "        [3,1,2],\n",
    "        [1,3,2],\n",
    "        [2,4],\n",
    "        [3,1,2],\n",
    "        [1,3,1,1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on built-in function sort:\n",
      "\n",
      "sort(*, key=None, reverse=False) method of builtins.list instance\n",
      "    Sort the list in ascending order and return None.\n",
      "    \n",
      "    The sort is in-place (i.e. the list itself is modified) and stable (i.e. the\n",
      "    order of two equal elements is maintained).\n",
      "    \n",
      "    If a key function is given, apply it once to each list item and sort them,\n",
      "    ascending or descending, according to their function values.\n",
      "    \n",
      "    The reverse flag can be set to sort in descending order.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(inputs.sort)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "inputs.sort(key=len, reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 2, 1], [1, 3, 1, 1], [1, 3, 2], [3, 1, 2], [3, 1, 2], [2, 4]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import accumulate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 6, 10]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(accumulate([1,2,3,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "wall = inputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "wall = [list(accumulate(l)) for l in wall]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 3, 5, 6], [1, 4, 5, 6], [1, 4, 6], [3, 4, 6], [3, 4, 6], [2, 6]]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wall"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 6]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_one = wall[0]\n",
    "longest_one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "for n in range(1, longest_one[-1]):\n",
    "    print(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "\n",
      "3\n",
      "1\n",
      "3\n",
      "2\n",
      "1\n",
      "4\n",
      "\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "wall_height = len(wall)\n",
    "index_list = [0 for i in range(wall_height)]\n",
    "print(wall_height)\n",
    "print()\n",
    "\n",
    "max_line_counting = 0\n",
    "for n in range(1, longest_one[-1]+1):\n",
    "    line_counting = 0\n",
    "    for row_index in range(wall_height):\n",
    "        if wall[row_index][index_list[row_index]] == n:\n",
    "            line_counting += 1\n",
    "        elif wall[row_index][index_list[row_index]] < n:\n",
    "            index_list[row_index] += 1\n",
    "    #cross_counting = wall_height - line_counting\n",
    "    #print(cross_counting)\n",
    "    print(line_counting)\n",
    "    if line_counting > max_line_counting:\n",
    "        max_line_counting = line_counting\n",
    "print()\n",
    "print(wall_height - max_line_counting)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "----\n",
      "[[1, 2], [2], [1, 2]]\n",
      "3\n",
      "\n",
      "the n: 1\n",
      "the value: 1\n",
      "the value: 2\n",
      "the value: 1\n",
      "2\n",
      "the n: 2\n",
      "the value: 2\n",
      "the value: 2\n",
      "the value: 2\n",
      "0\n",
      "\n",
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "from itertools import accumulate\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        base = wall[0]\n",
    "        if all([row == base and len(row)==1 for row in wall]):\n",
    "            return len(wall)\n",
    "        \n",
    "        wall = [list(accumulate(l)) for l in wall]\n",
    "        longest_one = wall[0]\n",
    "        wall_height = len(wall)\n",
    "        index_list = [0 for i in range(wall_height)]\n",
    "        length_list = [len(l) for l in wall]\n",
    "        print(wall)\n",
    "        print(wall_height)\n",
    "        print()\n",
    "\n",
    "        max_line_counting = 0\n",
    "        for n in range(1, longest_one[-1]+1):\n",
    "            print(\"the n:\", n)\n",
    "            line_counting = 0\n",
    "            for row_index in range(wall_height):\n",
    "                if wall[row_index][index_list[row_index]] < n:\n",
    "                    index_list[row_index] += 1\n",
    "                print(f\"the value: {wall[row_index][index_list[row_index]]}\") \n",
    "                if wall[row_index][index_list[row_index]] == n:\n",
    "                    #a = any([v < length_list[i] for i,v in enumerate(index_list)])\n",
    "                    b = wall[row_index][index_list[row_index]] != wall[row_index][-1]\n",
    "                    if (b):\n",
    "                        line_counting += 1\n",
    "            print(line_counting)\n",
    "            if line_counting > max_line_counting:\n",
    "                max_line_counting = line_counting\n",
    "        print()\n",
    "        print(wall_height - max_line_counting)\n",
    "        return wall_height - max_line_counting\n",
    "\n",
    "#inputs = [[1],[1],[1]] # 3\n",
    "#inputs = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] #2\n",
    "#inputs = [[7, 1, 2], [3, 5, 1, 1], [10]] #1\n",
    "#inputs = [[6, 2, 2], [1, 4, 4, 1], [2, 5, 3]] #2\n",
    "#inputs = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]#2\n",
    "#inputs = [[6, 2, 2], [1, 4, 4, 1], [2, 5, 3]] #2\n",
    "#inputs = [[7, 1, 2], [3, 5, 1, 1], [10]] #1\n",
    "inputs = [[1,1],[2],[1,1]] #1\n",
    "\n",
    "s = Solution()\n",
    "print('----')\n",
    "print(s.leastBricks(wall=inputs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/brick-wall\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "```python\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def leastBricks(self, wall: List[List[int]]) -> int:\n",
    "        base = wall[0]\n",
    "        if all([row == base and len(row)==1 for row in wall]):\n",
    "            return len(wall)\n",
    "        \n",
    "        wall = [list(accumulate(l)) for l in wall]\n",
    "        longest_one = wall[0]\n",
    "        wall_height = len(wall)\n",
    "        index_list = [0 for i in range(wall_height)]\n",
    "        length_list = [len(l) for l in wall]\n",
    "        print(wall)\n",
    "        print(wall_height)\n",
    "        print()\n",
    "\n",
    "        max_line_counting = 0\n",
    "        for n in range(1, longest_one[-1]+1):\n",
    "            #print(\"the n:\", n)\n",
    "            line_counting = 0\n",
    "            for row_index in range(wall_height):\n",
    "                if wall[row_index][index_list[row_index]] < n:\n",
    "                    index_list[row_index] += 1\n",
    "                #print(f\"the value: {wall[row_index][index_list[row_index]]}\") \n",
    "                if wall[row_index][index_list[row_index]] == n:\n",
    "                    #a = any([v < length_list[i] for i,v in enumerate(index_list)])\n",
    "                    b = wall[row_index][index_list[row_index]] != wall[row_index][-1]\n",
    "                    if (b):\n",
    "                        line_counting += 1\n",
    "            #print(line_counting)\n",
    "            if line_counting > max_line_counting:\n",
    "                max_line_counting = line_counting\n",
    "        #print()\n",
    "        #print(wall_height - max_line_counting)\n",
    "        return wall_height - max_line_counting\n",
    "```\n",
    "\n",
    "Spent two days"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}